This invention relates to data processing, and in particular to exclusive set systems such as can be used for cryptographic and other applications.
EXCLUSIVE SET SYSTEMS. In [8] Kumar and Russell formalized the notion of an exclusive set system, which is a family of sets for which every large subset of the universe can be written as the union of some collection of subsets from the family. More formally,
Definition 1. A family of subsets CC={S1, . . . , Sk} over [n] is (n,k,r,t)-exclusive if for any subset R⊂[n] with |R|≦r, we can write
            [      n      ]        ⁢    \    ⁢    R    =            ⋃              j        =        1            t        ⁢          S              i        j            for some 1≦ij≦k. Indices ij do not have to be distinct, so R can be the union of less than t distinct sets
  S      i    j  Here [n] denotes the set of positive integers {1, . . . , n}. Clearly, [n] can be replaced with any set U of n entities.
The family
  {            S              j        1              ,    …    ⁢                  ,          S              j        t              }is called a cover for the set [n]\R or a complement cover for R, and is sometimes denoted CR herein.
In the example of FIG. 1, the elements of [n] are shown as crosses in a two-dimensional plane. Each element iε[n] is marked with reference numeral 104.i. The set R consists of element 104.1, 104.2, 104.3 (r≧3). The set [n]\R is covered by three sets S1, S2, S3 (t≧3 and k≧3), where S1={4,5,6}, S2={6,7}, and S3={8}.
Determining the exact tradeoff between n,k,r, and t is a fundamental combinatorial problem with significant applications in computer science.
APPLICATION TO BROADCAST ENCRYPTION. In a broadcast encryption scheme, there is a server 210 (FIG. 2A) sending a broadcast to n clients 104.1-104.n. The broadcast content B is encrypted with some symmetric encryption algorithm 1 (as shown at 220) using a secret key bk. The encrypted content E1bk(B) is broadcast to the clients 104. Each client 104.i possesses an encryption key ki for a symmetric encryption algorithm 2. In this example, the set R of revoked clients consists of terminals {1, . . . , r}, i.e. {104.1, . . . , 104.r}. The server encrypts the key bk with the algorithm 2 (as shown at 230) n-r times using the respective keys kr+1, . . . , kn of the non-revoked clients. The resulting encryptions are shown as
      E    ⁢                  ⁢          2              k                  r          +          1                      ⁢          (      bk      )        ,  …  ⁢          ,      E    ⁢                  ⁢          2              k        n              ⁢                  (        bk        )            .      The server broadcasts these encryptions.
Each client 104 (FIG. 2B) receives these broadcasts. The non-revoked clients 104.r+1, . . . , 104.n each execute a decryption algorithm 2 (as shown at 240) corresponding to the encryption algorithm 2. At step 240, each of these clients i (i=r+1, . . . , n) uses the corresponding key ki and the encryption
  E  ⁢          ⁢      2          k      i        ⁢      (    bk    )  to recover the key bk. The key bk and the broadcast encryption E1bk(B) are then provided as inputs to a decryption algorithm 1 corresponding to the encryption algorithm 1, as shown at 250. The output is the broadcast content B.
The revoked clients 104.1, . . . , 104.r cannot recover the broadcast content B because they do not receive the encryptions of the broadcast key bk with the keys k1, . . . , kr. 
In this example, each broadcast includes n-r encryptions at step 230. The number of encryptions can be reduced to at most t if each set Si is associated with an encryption key
  k      S    i  provided to all clients 104 which are members of the set Si. See FIG. 3. The server determines the set cover
  {                              S                      i            j                          |        j            =      1        ,    …    ⁢                  ,    t    }for the set [n]\R. At step 230 (FIG. 4A), the server 210 encrypts the key bk using the corresponding keys
  k      S          i      j      . Since only the non-revoked clients each have one or more of the keys
      k          S              i        j              ,only these clients will be able to recover the key bk at step 240 (FIG. 4B) and recover the broadcast content B. At step 240, the client can use any key
  k      S          i      j      for the set
  S      i    j  to which the client belongs. Any coalition of the revoked members (revoked clients) learns no information from the broadcast even if they collude.
Since each subset of t keys can correspond to at most one set [n]\R, we need
            (                                    k                                                t                              )        ≥                  ∑                  i          =          0                r            ⁢              (                                            n                                                          i                                      )              ≥          (                                    n                                                r                              )        ,or equivalently,
  k  =            Ω      ⁡              (                              t            ⁡                          (                                                                    n                                                                                        r                                                              )                                            r            /            t                          )              .  (The lower bound we use here is the same as that given by Lemma 11 in [11], and is unknown to be tight for general n,r, and t. We note that the bounds in that paper are generally not tight.) For instance, their Theorem 12 can be improved by using the sunflower lemma with relaxed disjointness (p. 82 in [6]) instead of the sunflower lemma. This general technique of using exclusive set systems for broadcast encryption in known in the art as the subset-cover framework.
APPLICATION TO CERTIFICATE REVOCATION. In FIG. 5, elements 104 are digital certificates used in public key infrastructures (PKI) to facilitate secure use and management of public keys in a networked computer environment. Each certificate 104 contains a user's public key PK and the user's name and may also contain the user's email address or addresses, the certificate's serial number SN (generated by a certificate authority 610 (FIG. 6A) to simplify the certificate management), the certificate issue date D1, the expiration date D2, an identification of algorithms to be used with the public and secret keys, an identification of the CA 610, validity proof data 104-V (described below) and possibly other data. The data mentioned above is shown at 104D. Certificate 104 also contains CA's signature 104-SigCA on the data 104D. CA 610 sends the certificate 104 to the user's (key owner's) computer system (not shown). Either the owner or the CA 610 can distribute the certificate to other parties to inform them of the user's public key PK. Such parties can verify the CA's signature 104-SigCA with the CA's public key to ascertain that the certificate's public key PK does indeed belong to the person whose name and email address are provided in the certificate.
If a certificate 104 is revoked, other parties must be prevented from using the certificate. Validity proof data 104-V is used to ascertain that the certificate is valid. In existing certificate revocation schemes known in the art, such as the one of Micali [13,14,15] and subsequently by Aiello et al., [1], in each period m (e.g. each day), certificate authority 610 issues a validation proof cm for each non-revoked certificate in the public-key infrastructure. CA's clients 620 (FIG. 6B) provide the validation proof cm for the certificate with the certificate's validity data 104-V to a verification algorithm, as shown at 630. The verification algorithm's output indicates whether or not the certificate is valid in the period m.
In the original work of Micali, one validation proof was issued per non-revoked certificate. Thus the overall communication complexity of the system was proportional to n-r where n is the total number of users and r is the number of non-revoked certificates. Aiello et al. observed that instead of having one validity proof apply to one individual user, one could instead group users together into various subsets Si as in the definition 1. In FIGS. 3 and 6A, each subset Si is associated with cryptographic information ksi from which the CA can generate a validation proof cm(Si) for the period m. This single validation proof proves the validity of all the certificates in the subset Si. For each period m, the CA determines a cover { Sij } for the set of non-revoked certificates, computes the validation proofs cm(Sij ), and distributes the validation proofs to the clients 620 (which may include the certificate owners and/or other parties).
Since each subset Si must be provided with a validity proof cm(Si), the number of total validity proofs may increase, but the communication complexity for transmitting the proofs is now proportional to the t parameter in the underlying exclusive-set system, and generally speaking, t<n−r, so the overall communication needed for this approach is less than that needed for the original Micali approach.